class Node:
    def __init__(self, key=None, value=None):
        self.pre = self
        self.next = self
        self.key = key
        self.value = value

class LRUCache(object):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.capacity = capacity
        self.dict = {}
        self.head = Node()

    def get(self, key):
        """
        :rtype: int
        """
        if key in self.dict:
            node = self.dict[key]
            # retrive node from list
            node.pre.next = node.next
            node.next.pre = node.pre
            # add to head
            node.next = self.head.next
            node.pre = self.head
            node.next.pre = node
            node.pre.next = node
            return node.value
        else: 
            return -1

    def set(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: nothing
        """
        if key not in self.dict:
            if len(self.dict)>=self.capacity:
                # remove the recently least used node
                node = self.head.pre
                # retrive node from tail
                node.pre.next = node.next
                node.next.pre = node.pre
                del self.dict[node.key]
            # create new node
            node = Node(key, value)
            self.dict.update({key:node})
        else:
            node = self.dict[key]
            node.value = value
            # retrive the node
            node.pre.next = node.next
            node.next.pre = node.pre
        # add the head
        node.pre = self.head
        node.next = self.head.next
        node.pre.next = node
        node.next.pre = node